﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0136_SortColors : IAlgorithm
    {
        // 颜色分类

        // 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
        // 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
        // 必须在不使用库的sort函数的情况下解决这个问题。

        // 提示：
        //  n == nums.length
        //  1 <= n <= 300
        //  nums[i] 为 0、1 或 2

        // 进阶：
        //  你可以不使用代码库中的排序函数来解决这道题吗？
        //  你能想出一个仅使用常数空间的一趟扫描算法吗？

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 1, 2, 0, 1, 0, 2, 2, 1, 0 };
            // 算法执行与打印
            SortColors(nums);
            foreach (var item in nums)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        public void SortColors(int[] nums)
        {
            int l = 0;
            for (int i = 0; i < 3; i++)
                for (int j = l; j < nums.Length; j++)
                    if (nums[j] == i)
                    {
                        var temp = nums[l];
                        nums[l] = nums[j];
                        nums[j] = temp;
                        l++;
                    }
        }

        // 因为只有三个数，最小移到左边，最大移到右边，剩下的肯定在中间，因此一次遍历就可以解决
        public void SortColors1(int[] nums)
        {
            int left = 0, right = nums.Length - 1;   //left代表红色，right代表蓝色
            for (int i = 0; i <= right; i++)
            {
                if (nums[i] == 0)
                {
                    Swap(nums, left, i);
                    left++;
                }
                if (nums[i] == 2)
                {
                    Swap(nums, i, right);
                    right--;
                    i--;                     //防止漏算
                }
            }
        }
        private void Swap(int[] nums, int i, int j)
        {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

    }
}
